package JZOffer;

import java.util.Arrays;

/**
 * @author Lw中
 * @date 2021/8/15 22:26
 */
public class Jz39 {

    // Jz.39数组中出现次数超过一半的数字

    public int majorityElement(int[] nums) {
        // 方法一：因为次数超过数组总元素的一半，所以将数组排好序之后，中位数一定是出现次数草果一半的数字
        // Arrays.sort(nums);
        // return nums[nums.length / 2];
        // 方法二：摩尔投票法
        int vote = 0, x = 0;
        // 循环遍历数组元素
        for (int num : nums) {
            if (vote == 0) x = num;
            vote += num == x ? 1 : -1;
        }
        return x;
    }

}
